/**
 * 哈希表。
 */
#ifndef _AHAMOLETT_CLANG_SATASTRUCT_HSAH_TABLE_H_
#define _AHAMOLETT_CLANG_SATASTRUCT_HSAH_TABLE_H_

#include <cds/cds_types.h>
#include <cds/string.h>
#include <cds/hash.h>

/* 哈希链表节点。 */
struct hlist_node {
    struct hlist_node *next;    /// 指向后继节点的指针。
    struct hlist_node **pprev;  /// 指向前驱节点指向当前节点的指针，为一个双重指针。
};

/* 哈希链表的头结点。 */
struct hlist_head {
    struct hlist_node *first;   /// 指向第一个节点的指针。
};

/* 操作哈希表的函数指针集。 */
struct hash_table_opts {
    /**
     * @brief 哈希表获得节点哈希值的成员函数指针。
     * 
     * @param $0 unsigned long 计算哈希值的数据。
     * 
     * @return unsigned long 计算得到的哈希值。
     */
    unsigned long (*hash_func)(unsigned long);
    /**
     * @brief 对比哈希表中两个数据的大小关系。
     * 
     * @param $0 unsigned long 计算哈希值的数据。
     * @param $1 unsigned long 计算哈希值的数据。
     * 
     * @return int 当 $1 > $2 时大于0， $1 == $2 时等于0， $1 < $2 时小于0。
     */
    int (*cmp_func)(unsigned long, unsigned long);
    /**
     * @brief 获得一个哈希节点的键值。
     * 
     * @param $0 获得键值的哈希节点。
     * 
     * @return unsigned long 哈希节点的键值。
     */
    unsigned long (*get_key_func)(struct hlist_node*);
};

/* 哈希表表头。 */
struct hash_table{
    unsigned long bucket_num;   /// 哈希桶的数量，即 buckets 成员数组的长度。
    unsigned long nums; /// 当前哈希表中的元素数量。
    struct hlist_head *buckets; /// 哈希桶数组，链接了哈希表中所有的成员节点。
    struct hash_table_opts *opts;   /// 操作哈希表的函数指针集。
};

/**
 * @brief 哈希表获得节点哈希值的成员函数指针。
 * 
 * @param htab 哈希节点所在哈希表。
 * @param val unsigned long 计算哈希值的数据。
 * 
 * @return unsigned long 计算得到的哈希值。
 */
#define htab_hash(htab, val)   ((htab)->opts->hash_func(val))

/**
 * @brief 对比哈希表中两个数据的大小关系。
 * 
 * @param htab 哈希节点所在哈希表。
 * @param key1 unsigned long 计算哈希值的数据。
 * @param key2 unsigned long 计算哈希值的数据。
 * 
 * @return int 当 key1 > key2 时大于0， key1 == key2 时等于0， key1 < key2 时小于0。
 */
#define htab_keys_cmp(htab, key1, key2) ((htab)->opts->cmp_func(key1, key2))

/**
 * @brief 获得一个哈希节点的键值。
 * 
 * @param htab 哈希节点所在哈希表。
 * @param node struct hlist_node* 获得键值的哈希节点。
 * 
 * @return unsigned long 哈希节点的键值。
 */
#define htab_get_key(htab, node)    ((htab)->opts->get_key_func(node))

/**
 * @brief 判断一个哈希桶是否为空。
 * 
 * @param head struct hlist_head* 哈希桶的头结点。
 * 
 * @retval true 哈希桶为空。
 * @retval false 哈希桶不为空。
 */
#define hlist_empty(head)   ((head)->first == NULL)

/**
 * @brief 判断一个哈希节点是否位于哈希桶中。
 * 
 * @param node 哈希节点。
 * 
 * @retval true 哈希节点位于哈希桶中。
 * @retval false 哈希节点不位于哈希桶中。
 */
#define hlist_unhashed(node)    ((node)->pprev != NULL)

/**
 * @brief 获得一个哈希桶中的第一个哈希节点。
 * 
 * @param head struct hlist_head* 哈希桶。
 * 
 * @return struct hlist_node* 如果有第一个节点，返回这个节点，否则返回 NULL 。
 */
#define first_hlist_node_safe(head)    ({  \
    struct hlist_node *__node = NULL;   \
    if ((head) != NULL) {   \
        __node = (head)->first; \
    }   \
    __node; \
})

/**
 * @brief 获得一个哈希节点的下一个哈希节点。
 * 
 * @param head struct hlist_node* 哈希节点。
 * 
 * @return struct hlist_node* 如果有下一个哈希节点，返回下一个哈希节点，否则返回 NULL 。
 */
#define next_hlist_node_safe(node) ({  \
    struct hlist_node *__node = NULL;   \
    if ((node) != NULL) {   \
        __node = (node)->next;  \
    }   \
    __node; \
})

/**
 * @brief 获得一个哈希桶中的第一个哈希节点所在的结构体。
 * 
 * @param head struct hlist_head* 哈希桶。
 * @param type 哈希节点所在结构体的数据类型。
 * @param member 哈希节点入口在其所在结构体内的成员名。
 * 
 * @return struct hlist_node* 如果有第一个节点，返回这个节点所在结构体，否则返回 NULL 。
 */
#define first_hlist_node_entry_safe(head, type, member) ({  \
    type *__ptr = NULL; \
    struct hlist_node *__node = first_hlist_node_safe(head);    \
    if (__node != NULL) {   \
        __ptr = container_of(__node, type, member); \
    }   \
    __ptr;  \
})

/**
 * @brief 获得一个哈希桶中的下一个哈希节点所在的结构体。
 * 
 * @param node type* 哈希桶。
 * @param member 哈希节点入口在其所在结构体内的成员名。
 * 
 * @return struct hlist_node* 如果有第下个节点，返回下一个节点所在结构体，否则返回 NULL 。
 */
#define next_hlist_node_entry_safe(node, member)    ({  \
    typeof(node) __ptr = NULL;  \
    if ((node) != NULL) {   \
        struct hlist_node *__node = next_hlist_node_safe(&(node)->member);  \
        if (__node != NULL) {   \
            __ptr = container_of(__node, typeof(*(node)), member);  \
        }   \
    }   \
    __ptr;  \
})

/**
 * @brief 获得一个哈希表内第一个哈希桶的哈希头结点。
 * 
 * @param htab 哈希表结构体。
 * 
 * @return struct hlist_node* 哈希表有效时返回第一个哈希桶的头结点，否则返回 NULL 。
 */
extern struct hlist_head *first_hlist_head_safe(struct hash_table *htab);

/**
 * @brief 获得一个哈希表内下一个哈希桶的哈希头结点。
 * 
 * @param htab 哈希表结构体。
 * @param head 当前的哈希桶头结点。
 * 
 * @return struct hlist_node* 有下一个哈希桶时返回下一个哈希桶的头结点，否则返回 NULL 。
 */
extern struct hlist_head *next_hlist_head_safe(
    struct hash_table *htab,
    struct hlist_head *head
);

/**
 * @brief 初始化一个哈希表。
 * 
 * 先检查输入参数的有效性，如果输入的参数有效，则根据这些参数初始化哈希表头。
 * 
 * @param htab 进行初始化的哈希表表头。
 * @param buckets 指向当前哈希表的哈希桶数组。
 * @param bucket_num 哈希表中哈希桶的数量，哈希桶数组的长度。
 * @param opts 操作哈希表的函数指针集。
 * 
 * @return struct hash_table* 初始化成功返回初始化后的哈希表，失败返回NULL。
 */
extern struct hash_table *init_hash_table(
    struct hash_table *htab,
    struct hlist_head *buckets,
    unsigned long bucket_num,
    struct hash_table_opts *opts
);

/**
 * @brief 初始化一个哈希节点。
 * 
 * 将一个哈希节点初始化为空节点。
 * 
 * @param hnode 进行初始化的哈希节点。
 */
extern void init_hash_node(struct hlist_node *hnode);

/**
 * @brief 插入一个哈希节点。
 * 
 * 尝试将一个哈希节点插入哈希表中，并根据输入参数决定是在遇到键值冲突时替换掉原有的哈希节点。
 * 
 * @param htab 进行插入操作的哈希表。
 * @param node 被插入的哈希节点。
 * @param replace 作为布尔值，为 true 时会替换掉原本的节点，为 false 时不会替换原本的节点。
 * 
 * @return struct hlist_node* 插入成功且哈希表中原本没有与新插入节点键值相同的节点，返回
 *                            被插入的哈希节点；如果新插入节点的键值与哈希表中原本的某个
 *                            节点键值相同，则返回哈希表中的这个哈希节点；如果上述情况都
 *                            不满足，返回 NULL 。
 */
extern struct hlist_node *insert_hash_node(
    struct hash_table *htab,
    struct hlist_node *node,
    int replace
);

/**
 * @brief 查找一个哈希节点。
 * 
 * 通过一个哈希节点的键值，在哈希表中查找对应键值的节点。
 * 
 * @param htab 进行查找的哈希表。
 * @param key 目标哈希节点的键值。
 * 
 * @return struct hlist_node* 查找成功返回对应的哈希节点，查找失败返回 NULL 。
 */
extern struct hlist_node *find_key_hash_node(
    struct hash_table *htab,
    unsigned long key
);

/**
 * @brief 在哈希表中删除一个哈希节点。
 * 
 * 给定一个哈希节点，并将其删除。该函数不会检查哈希节点是否真的在哈希表中，如果删除了一个不在
 * 给定哈希表中的节点，会引起 BUG 。
 * 
 * @param htab 哈希表。
 * @param node 被删除的哈希节点。
 * 
 * @return struct hlist_node* 删除成功返回被删除的哈希节点，删除失败返回 NULL 。
 */
extern struct hlist_node *del_hash_node(
    struct hash_table *htab,
    struct hlist_node *node
);

/**
 * @brief 根据键值在哈希表中找到对应的哈希节点，并将其是删除。
 * 
 * @param htab 哈希表。
 * @param key 需要被删除的哈希节点的键值。
 * 
 * @return struct hlist_node* 删除成功返回被删除的哈希节点，失败返回 NULL 。
 */
extern struct hlist_node *del_key_hash_node(
    struct hash_table *htab,
    unsigned long key
);

/**
 * @brief 顺序遍历一个哈希表内的所有哈希桶。
 * 
 * @param htab 进行遍历的哈希表。
 * @param pos 作为游标遍历哈希桶。
 */
#define htable_foreach_hlist_head(htab, pos)    \
    for ((pos) = first_hlist_head_safe(htab);   \
        (pos) != NULL;  \
        (pos) = next_hlist_head_safe(htab, pos) \
    )

/**
 * @brief 顺序遍历 hlist_head 结构体指向的整个哈希链表节点所在的结构体。
 * 
 * @param head 进行遍历的哈希链表头结点。
 * @param pos 作为游标保存当前节点的指针。
 * @param n 存放提前获得的下一个节点的指针。
 * @param member 哈希节点在其所在结构体内的成员名。
 */
#define hlist_foreach_entry_safe(head, pos, n, member)  \
    for ((pos) = first_hlist_node_entry_safe(head, typeof(*(pos)), member), \
        (n) = next_hlist_node_entry_safe(pos, member);  \
        (pos) != NULL;  \
        (pos) = (n),    \
        (n) = next_hlist_node_entry_safe(n, member) \
    )

/**
 * @brief 遍历整个哈希表节点所链接的结构体。
 * 
 * 分别利用对哈希桶和对单个哈希桶内节点的遍历，遍历整个哈希表。由于哈希表的特性，大部分情况下
 * 遍历节点的顺序是乱序的。
 * 
 * @param htab 进行遍历的哈希表。
 * @param buc 作为游标遍历哈希桶。
 * @param pos 作为游标保存当前节点的指针。
 * @param n 存放提前获得的下一个节点的指针。
 * @param member 哈希节点在其所在结构体内的成员名。
 */
#define htable_foreach_entry_safe(htab, buc, pos, n, member)    \
    htable_foreach_hlist_head(htab, buc)    \
    hlist_foreach_entry_safe(buc, pos, n, member)


#endif
